﻿// 二分搜索算法.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <time.h>
#include <stdlib.h>
#include <algorithm>

// 二分搜索算法
int BinarySearch(int arr[], int size, int val)
{
    int f = 0;
    int l = size - 1;
    int mid = (l + f) / 2;
    while (arr[mid] != val)
    {
        if (arr[mid] > val)
            l = mid - 1;
        else
            f = mid + 1;
        if (l < f)
            return -1;
        mid = (l + f) / 2;
    }
    return mid;
}




// 二分搜索算法
//二分搜索算法相当于构建了一个完整的二叉树，它的时间复杂度就是树的层高L=log2 n；即O（log2n）

int main()
{
    long start, end;
    int idx;
    srand(time(0));
    int* arr = (int*)malloc(10000 * sizeof(int));

    for (int i = 0; i < 10000; i++)
    {
        arr[i] = rand();
    }

    arr[9008] = 1234;
    std::sort(arr, arr + 10000);//c++ sort可以排序无序数字，头文件为#include <algorithm>

 
    start = clock();
    idx = BinarySearch(arr, 10000, 1234);
    end = clock();
    printf("BinarySearch time:%dms idx:%d\n", end - start, idx);
}
